[洛谷P1908]逆序对

发表于 | 分类于 ， | | 阅读次数:

题目

题目描述

猫猫TOM和小老鼠JERRY最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。最近，TOM老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中ai>aj且i<j的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。

输入格式

第一行，一个数n，表示序列中有n个数。
第二行n个数，表示给定的序列。

输出格式

给定序列中逆序对的数目。

输入样例

1
2
6
5 4 2 6 3 1

输出样例

1
11

说明

对于50%的数据，n≤2500
对于100%的数据，n≤40000。

题解

树状数组

既然名字都叫树状数组，那么肯定是和数有关的咯，我们来先看一个二叉树

二叉树

我们来稍微变下形

变形

现在我们把树状数组c[]摆放到每一列的顶端

顶端

C[i]代表子树的叶子结点的权值之和
我们通过这张图可以知道
$$ C[1]=A[1]; $$
$$ C[2]=A[1]+A[2]; $$
$$ C[3]=A[3]; $$
$$ C[4]=A[1]+A[2]+A[3]+A[4]; $$
$$ C[5]=A[5]; $$
$$ C[6]=A[5]+A[6]; $$
$$ C[7]=A[7]; $$
$$ C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8]; $$
通过分情况讨论好像是有什么规律，那有没有更一般的规律呢？
我们不妨将树状数组的编号转换成二进制看看
二进制
$$ 1=(001)—C[1]=A[1]; $$
$$ 2=(010)—C[2]=A[1]+A[2]; $$
$$ 3=(011)—C[3]=A[3]; $$
$$ 4=(100)—C[4]=A[1]+A[2]+A[3]+A[4]; $$
$$ 5=(101)—C[5]=A[5]; $$
$$ 6=(110)—C[6]=A[5]+A[6]; $$
$$ 7=(111)—C[7]=A[7]; $$
$$ 8=(1000)—C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8]; $$

对照式子可以发现 C[i]=A[i-2^k+1]+A[i-2^k+2]+……A[i]; （k为i的二进制中从最低位到高位连续零的长度）例如i=8时，k=3。

而lowbit(x)函数的作用就是取出x的最低位。

树状数组的优点在于单点更新以及区间查询，对于求逆序对来说，知道一个数的位置x，那么1~x范围内就是比它小的数，而用已经插入的数的个数减去这个数，累加起来就是我们要算的逆序对数。

离散化

上面提到我们要知道一个数的位置，可以用树状数组下标来表示$ c[x] $，但整型范围很大,不可能开这么大的数组，所以我们只需要保留它们的相对大小，用离散化处理。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 100001
using namespace std;
int n;
struct node{
	int num,index;
}a[MAXN];
int c[MAXN];//树状数组
int A[MAXN];//离散化后的数组

int low_bit(int i)
{
    return i&(-i);
}
void update(int i,int v)//插入
{
    while(i<=n){
        c[i]+=v;
        i+=low_bit(i);
    }
}
int get_sum(int i)//区间查找
{
    int res=0;
    while(i){
        res+=c[i];
        i-=low_bit(i);
    }
    return res;
}
bool cmp(node a,node b)  
{  
    return a.num<b.num;  
}  

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i].num);
		a[i].index=i;
	}
	sort(a+1,a+1+n,cmp); 
	int p=0;
	for(int i=1;i<=n;i++){
		/*if(a[i].num!=a[i-1].num)p++;
		A[a[i].index]=p;*///如果数据中存在重复数据才需要
		A[a[i].index]=i;//离散化
	}
	long long ans=0;
	for(int i=1;i<=n;i++){
		update(A[i],1);//插入
		ans+=i-get_sum(A[i]);
	}
	printf("%lld",ans);
	return 0;
}